{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Count Collisions on a Road"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Medium"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #stack #string"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #栈 #字符串"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: countCollisions"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #统计道路上的碰撞次数"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>在一条无限长的公路上有 <code>n</code> 辆汽车正在行驶。汽车按从左到右的顺序按从 <code>0</code> 到 <code>n - 1</code> 编号，每辆车都在一个 <strong>独特的</strong> 位置。</p>\n",
    "\n",
    "<p>给你一个下标从 <strong>0</strong> 开始的字符串 <code>directions</code> ，长度为 <code>n</code> 。<code>directions[i]</code> 可以是 <code>'L'</code>、<code>'R'</code> 或 <code>'S'</code> 分别表示第 <code>i</code> 辆车是向 <strong>左</strong> 、向 <strong>右</strong> 或者 <strong>停留</strong> 在当前位置。每辆车移动时 <strong>速度相同</strong> 。</p>\n",
    "\n",
    "<p>碰撞次数可以按下述方式计算：</p>\n",
    "\n",
    "<ul>\n",
    "\t<li>当两辆移动方向&nbsp;<strong>相反</strong>&nbsp;的车相撞时，碰撞次数加 <code>2</code> 。</li>\n",
    "\t<li>当一辆移动的车和一辆静止的车相撞时，碰撞次数加 <code>1</code> 。</li>\n",
    "</ul>\n",
    "\n",
    "<p>碰撞发生后，涉及的车辆将无法继续移动并停留在碰撞位置。除此之外，汽车不能改变它们的状态或移动方向。</p>\n",
    "\n",
    "<p>返回在这条道路上发生的 <strong>碰撞总次数</strong> 。</p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>directions = \"RLRSLL\"\n",
    "<strong>输出：</strong>5\n",
    "<strong>解释：</strong>\n",
    "将会在道路上发生的碰撞列出如下：\n",
    "- 车 0 和车 1 会互相碰撞。由于它们按相反方向移动，碰撞数量变为 0 + 2 = 2 。\n",
    "- 车 2 和车 3 会互相碰撞。由于 3 是静止的，碰撞数量变为 2 + 1 = 3 。\n",
    "- 车 3 和车 4 会互相碰撞。由于 3 是静止的，碰撞数量变为 3 + 1 = 4 。\n",
    "- 车 4 和车 5 会互相碰撞。在车 4 和车 3 碰撞之后，车 4 会待在碰撞位置，接着和车 5 碰撞。碰撞数量变为 4 + 1 = 5 。\n",
    "因此，将会在道路上发生的碰撞总次数是 5 。\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>directions = \"LLRR\"\n",
    "<strong>输出：</strong>0\n",
    "<strong>解释：</strong>\n",
    "不存在会发生碰撞的车辆。因此，将会在道路上发生的碰撞总次数是 0 。</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>1 &lt;= directions.length &lt;= 10<sup>5</sup></code></li>\n",
    "\t<li><code>directions[i]</code> 的值为 <code>'L'</code>、<code>'R'</code> 或 <code>'S'</code></li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [count-collisions-on-a-road](https://leetcode.cn/problems/count-collisions-on-a-road/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [count-collisions-on-a-road](https://leetcode.cn/problems/count-collisions-on-a-road/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['\"RLRSLL\"', '\"LLRR\"']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countCollisions(self, directions: str) -> int:\n",
    "        n=len(directions)\n",
    "        l,r=0,n-1\n",
    "        res=0\n",
    "        while l<n and directions[l]=='L':\n",
    "            l+=1\n",
    "        while r>=0 and directions[r]=='R':\n",
    "            r-=1\n",
    "        if l>=r:\n",
    "            return res\n",
    "        for i in range(l,r+1):\n",
    "            if directions[i]!='S':\n",
    "                res+=1\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countCollisions(self, s: str) -> int:\n",
    "        return len(s.lstrip('L').rstrip('R')) - s.count('S')\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countCollisions(self, directions: str) -> int:\n",
    "        directions = directions.lstrip('L')\n",
    "        directions = directions.rstrip(\"R\")\n",
    "        return len(directions) - directions.count(\"S\")"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countCollisions(self, directions: str) -> int:\n",
    "        directions = directions.lstrip(\"L\")\n",
    "        directions = directions.rstrip(\"R\")\n",
    "        return len(directions) - directions.count(\"S\")"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countCollisions(self, s: str) -> int:\n",
    "        s = s.lstrip('L')  # 前缀向左的车不会发生碰撞\n",
    "        s = s.rstrip('R')  # 后缀向右的车不会发生碰撞\n",
    "        return len(s) - s.count('S')  # 剩下非停止的车必然会碰撞\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "ptnL = re.compile('L+')\n",
    "ptnR = re.compile('R+')\n",
    "\n",
    "class Solution:\n",
    "    def countCollisions(self, directions: str) -> int:\n",
    "        n = len(directions)\n",
    "        if m := ptnL.match(directions):\n",
    "            n -= m.end() - m.start()\n",
    "        if m := ptnR.match(directions[::-1]):\n",
    "            n -= m.end() - m.start()\n",
    "        \n",
    "        return n - directions.count('S')"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countCollisions(self, directions: str) -> int:\n",
    "        s = directions.lstrip('L').rstrip('R')\n",
    "        return len(s) - s.count('S')"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countCollisions(self, directions: str) -> int:\n",
    "        directions = directions.lstrip('L')  # 前缀向左的车不会发生碰撞\n",
    "        directions = directions.rstrip('R')  # 后缀向右的车不会发生碰撞\n",
    "        return len(directions) - directions.count('S')  # 剩下非停止的车必然会碰撞"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countCollisions(self, directions: str) -> int:\n",
    "        left = 0\n",
    "        while left < len(directions) and directions[left] == \"L\":\n",
    "            left += 1\n",
    "        right = len(directions) - 1\n",
    "        while right >= 0 and directions[right] == \"R\":\n",
    "            right -= 1\n",
    "        cnt = 0\n",
    "        for i in range(left, right + 1):\n",
    "            if directions[i] == \"S\":\n",
    "                cnt += 1\n",
    "        return right - left + 1-cnt"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countCollisions(self, directions: str) -> int:\n",
    "        ans = 0\n",
    "        directions = directions.lstrip('L').rstrip('R') # 左边的L和右边的R都不会撞，其它的LR都会\n",
    "        return len(directions) - directions.count('S')"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countCollisions(self, directions: str) -> int:\n",
    "        n = len(directions)\n",
    "        l = 0\n",
    "        for x in directions:\n",
    "            if x == 'L':\n",
    "                l += 1\n",
    "            else:\n",
    "                break\n",
    "        r = 0\n",
    "        for y in directions[::-1]:\n",
    "            if y == 'R':\n",
    "                r += 1\n",
    "            else:\n",
    "                break\n",
    "        cnt = Counter(directions)\n",
    "        return n - l - r - cnt['S']\n",
    "              \n",
    "            \n",
    "            \n",
    "        \n",
    "                "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countCollisions(self, directions: str) -> int:\n",
    "        directions = directions.lstrip(\"L\")\n",
    "        directions = directions.rstrip(\"R\")\n",
    "        directions = directions.strip(\"S\")\n",
    "        return len(directions) - directions.count(\"S\")"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countCollisions(self, directions: str) -> int:\n",
    "        directions= directions.lstrip('L')\n",
    "        directions= directions.rstrip('R')\n",
    "        return len(directions)-directions.count('S')\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countCollisions(self, directions: str) -> int:\n",
    "        n = len(directions)\n",
    "        l, r = 0, n - 1\n",
    "        while l < n and directions[l] == 'L':\n",
    "            l += 1\n",
    "        while r >= 0 and directions[r] == 'R':\n",
    "            r -= 1\n",
    "        ans = 0\n",
    "        while l <= r:\n",
    "            if directions[l] != 'S':\n",
    "                ans += 1\n",
    "            l += 1\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countCollisions(self, directions: str) -> int:\n",
    "        directions = directions.lstrip('L')  # 前缀向左的车不会发生碰撞\n",
    "        directions = directions.rstrip('R')  # 后缀向右的车不会发生碰撞\n",
    "        return len(directions) - directions.count('S') "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countCollisions(self, s: str) -> int:\n",
    "        s = s.lstrip('L')  # 前缀向左的车不会发生碰撞\n",
    "        s = s.rstrip('R')  # 后缀向右的车不会发生碰撞\n",
    "        return len(s) - s.count('S')  # 剩下非停止的车必然会碰撞\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countCollisions(self, directions: str) -> int:\n",
    "        s = directions.lstrip('L')\n",
    "        s = s.rstrip('R')\n",
    "        return len(s) - s.count('S')"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countCollisions(self, s: str) -> int:\n",
    "        s = s.lstrip('L')  # 前缀向左的车不会发生碰撞\n",
    "        s = s.rstrip('R')  # 后缀向右的车不会发生碰撞\n",
    "        return len(s) - s.count('S')  # 剩下非停止的车必然会碰撞\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "ptnL = re.compile('L+')\n",
    "ptnR = re.compile('R+')\n",
    "\n",
    "class Solution:\n",
    "    def countCollisions(self, directions: str) -> int:\n",
    "        n = len(directions)\n",
    "        if m := ptnL.match(directions):\n",
    "            n -= m.end() - m.start()\n",
    "        if m := ptnR.match(directions[::-1]):\n",
    "            n -= m.end() - m.start()\n",
    "        \n",
    "        return n - directions.count('S')"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countCollisions(self, directions: str) -> int:\n",
    "        directions = directions.lstrip('L')  # 前缀向左的车不会发生碰撞\n",
    "        directions = directions.rstrip('R')  # 后缀向右的车不会发生碰撞\n",
    "        return len(directions) - directions.count('S')  # 剩下非停止的车必然会碰撞"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countCollisions(self, s: str) -> int:\n",
    "        s = s.lstrip('L') # 前缀向左的车不会发生碰撞\n",
    "        s = s.rstrip('R') # 后缀向右的车不会发生碰撞\n",
    "\n",
    "        return len(s) - s.count('S') # 剩余非停止的车必然碰撞"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def countCollisions(self, s: str) -> int:\n",
    "        s = s.lstrip('L')  # 前缀向左的车不会发生碰撞\n",
    "        s = s.rstrip('R')  # 后缀向右的车不会发生碰撞\n",
    "        return len(s) - s.count('S')  # 剩下非停止的车必然会碰撞"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countCollisions(self, directions: str) -> int:\n",
    "        s = directions\n",
    "        s = s.lstrip('L')\n",
    "        s = s.rstrip('R')\n",
    "        return len(s) - s.count('S')"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countCollisions(self, directions: str) -> int:\n",
    "        ret = 0\n",
    "        d = ''\n",
    "        r = 0\n",
    "        for x in directions:\n",
    "            oldret = ret\n",
    "            if x == 'L':\n",
    "                if d == 'S':\n",
    "                    ret += 1\n",
    "                elif d == 'R':\n",
    "                    ret += r + 1\n",
    "                    r = 0\n",
    "            elif x == 'S':\n",
    "                if d == 'R':\n",
    "                    ret += r\n",
    "                    r = 0\n",
    "            else:\n",
    "                r += 1\n",
    "            if oldret == ret:\n",
    "                d = x\n",
    "            else:\n",
    "                d = 'S'\n",
    "        return ret"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countCollisions(self, directions: str) -> int:\n",
    "        n = len(directions)\n",
    "        begin, end = 0, n\n",
    "        for i in range(n):\n",
    "            if directions[i] == \"L\":\n",
    "                begin += 1\n",
    "            else:\n",
    "                break\n",
    "        for i in range(n-1, -1, -1):\n",
    "            if directions[i] == \"R\":\n",
    "                end -= 1\n",
    "            else:\n",
    "                break\n",
    "   \n",
    "        return end - begin - directions[begin:end].count(\"S\")"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countCollisions(self, directions: str) -> int:\n",
    "        n =len(directions)\n",
    "        res=0\n",
    "        left = n\n",
    "        right = 0\n",
    "        if n ==1:\n",
    "            return 0\n",
    "        for i in range(n):\n",
    "            if directions[i] == \"S\" or directions[i] == \"R\":\n",
    "                left = i\n",
    "                break\n",
    "        print(left)\n",
    "        for i in range(n-1,0,-1):\n",
    "            if directions[i] == \"S\" or directions[i] == \"L\":\n",
    "                right = i\n",
    "                break\n",
    "        print(right)\n",
    "        if left<right:\n",
    "            for i in range(left,right+1):\n",
    "                if directions[i] ==\"S\":\n",
    "                    res+=1\n",
    "        res = right-left+1-res\n",
    "        return res\n",
    "        \n",
    "\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countCollisions(self, directions: str) -> int:\n",
    "        directions = directions.lstrip('L')  # 前缀向左的车不会发生碰撞\n",
    "        directions = directions.rstrip('R')  # 后缀向右的车不会发生碰撞\n",
    "        return len(directions) - directions.count('S') "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countCollisions(self, directions: str) -> int:\n",
    "        t = 0\n",
    "        n = len(directions)\n",
    "\n",
    "        f = True\n",
    "        i = 0\n",
    "        while i < n:\n",
    "            if directions[i] == 'L':\n",
    "                while i < n and directions[i] == 'L': i += 1\n",
    "                break\n",
    "            else:\n",
    "                f = False\n",
    "                break\n",
    "        if f:\n",
    "            t += i\n",
    "\n",
    "        f = True\n",
    "        i = n - 1\n",
    "        while i >= 0:\n",
    "            if directions[i] == 'R':\n",
    "                while i >=0 and directions[i] == 'R': i -= 1\n",
    "                break\n",
    "            else:\n",
    "                f = False\n",
    "                break\n",
    "        if f:\n",
    "            t += n - 1 - i\n",
    "\n",
    "        return n - t - directions.count('S')"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countCollisions(self, directions: str) -> int:\n",
    "        n = len(directions)\n",
    "        left = 0\n",
    "        while left < n and directions[left] == 'L':\n",
    "            left += 1\n",
    "        if left == n:\n",
    "            return 0\n",
    "        right = n - 1\n",
    "        while right >= 0 and directions[right] == 'R':\n",
    "            right -= 1\n",
    "        res = 0\n",
    "        for i in range(left, right + 1):\n",
    "            if directions[i] != 'S':\n",
    "                res += 1\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countCollisions(self, directions: str) -> int:\n",
    "        x0=-1\n",
    "        for i,ch in enumerate(directions):\n",
    "            if ch!='L':\n",
    "                x0=i \n",
    "                break\n",
    "        if x0==-1:\n",
    "            return 0\n",
    "        x1=-1\n",
    "        for i in range(len(directions)-1,-1,-1):\n",
    "            if directions[i]!='R':\n",
    "                x1=i \n",
    "                break\n",
    "        if x1==-1:\n",
    "            return 0\n",
    "        ans=0\n",
    "        for i in range(x0,x1+1):\n",
    "            if directions[i]!='S':\n",
    "                ans+=1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countCollisions(self, directions: str) -> int:\n",
    "        i = 0\n",
    "        j = len(directions) - 1\n",
    "        while i <= len(directions) - 1:\n",
    "            if directions[i] == 'L': i += 1\n",
    "            else: break\n",
    "        while j >= 0:\n",
    "            if directions[j] == 'R': j -= 1\n",
    "            else: break\n",
    "        ans = j - i + 1\n",
    "        while i <= j:\n",
    "            if directions[i] == 'S': ans -= 1\n",
    "            i += 1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countCollisions(self, directions: str) -> int:\n",
    "        # 整体上看 \"去掉往左右两边开的车之后，剩下非停止的车必然会碰撞。\"\n",
    "        # 思路 >>>  模拟\n",
    "        directions = directions.lstrip('L')\n",
    "        directions = directions.rstrip('R')\n",
    "        return len(directions) - directions.count('S')\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countCollisions(self, s: str) -> int:\n",
    "        s = s.lstrip('L')  # 前缀向左的车不会发生碰撞\n",
    "        s = s.rstrip('R')  # 后缀向右的车不会发生碰撞\n",
    "        return len(s) - s.count('S')  # 剩下非停止的车必然会碰撞\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countCollisions(self, directions: str) -> int:\n",
    "        res = 0\n",
    "        \n",
    "        for i, d in enumerate(directions):\n",
    "            if d == 'L':\n",
    "                if 'R' in directions[:i] or 'S' in directions[:i]:\n",
    "                    res += 1\n",
    "            if d == 'R':\n",
    "                if 'L' in directions[i+1:] or 'S' in directions[i+1:]:\n",
    "                    res += 1\n",
    "            \n",
    "        \n",
    "        return res \n",
    "                \n",
    "            \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countCollisions(self, directions: str) -> int:\n",
    "        s = directions.lstrip('L')\n",
    "        s = s.rstrip(\"R\")\n",
    "        return len(s) - s.count('S')\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countCollisions(self, directions: str) -> int:\n",
    "        directions = directions.lstrip('L')\n",
    "        directions = directions.rstrip('R')\n",
    "        return len(directions) - directions.count('S')\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countCollisions(self, directions: str) -> int:\n",
    "        res = 0\n",
    "        n = len(directions)\n",
    "        i = 0\n",
    "        iss = 0\n",
    "        r = 0\n",
    "        while i < n:\n",
    "            if i != n-1 and directions[i] == 'R' and directions[i+1] != 'R':\n",
    "                res = res + 1 + r if directions[i+1] == 'S' else res + 2 + r\n",
    "                r = 0\n",
    "                iss = 1\n",
    "                i += 1\n",
    "            elif directions[i] == 'R':\n",
    "                r += 1\n",
    "            elif directions[i] == 'L' and iss:\n",
    "                res += 1\n",
    "            elif directions[i] == 'S':\n",
    "                iss = 1\n",
    "            i += 1\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countCollisions(self, directions: str) -> int:\n",
    "        ans = 0\n",
    "        L = ['RL', 'SL']\n",
    "        R = ['RL', 'RS']\n",
    "        \n",
    "        # 只统计L，解决SLLL的情况\n",
    "        pre = directions[0]\n",
    "        for car in directions[1:]:\n",
    "            pair = pre+car\n",
    "            pre = car\n",
    "            if pair in L:\n",
    "                ans += 1\n",
    "                pre = 'S'\n",
    "\n",
    "        # 只统计R，解决RRRL的情况\n",
    "        pre = directions[-1]\n",
    "        for car in directions[:-1][::-1]:\n",
    "            pair = car+pre\n",
    "            pre = car\n",
    "            if pair in R:\n",
    "                ans += 1\n",
    "                pre = 'S'\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countCollisions(self, s: str) -> int:\n",
    "        s = s.lstrip('L')  # 前缀向左的车不会发生碰撞\n",
    "        s = s.rstrip('R')  # 后缀向右的车不会发生碰撞\n",
    "        return len(s) - s.count('S')  # 剩下非停止的车必然会碰撞\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countCollisions(self, directions: str) -> int:\n",
    "        directions = directions.lstrip('L')\n",
    "        directions = directions.rstrip('R')\n",
    "        return len(directions) - directions.count('S')"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countCollisions(self, directions: str) -> int:\n",
    "        left = {'R' : 2 ,'S' : 1, 'L':1}\n",
    "        ans = 0\n",
    "        left_flag = 0\n",
    "        right_flag = len(directions) - 1\n",
    "        while directions[left_flag] == 'L' and left_flag <= right_flag:\n",
    "            left_flag += 1\n",
    "            if left_flag >= right_flag :\n",
    "                break\n",
    "        while directions[right_flag] == 'R' and right_flag >= left_flag:\n",
    "            right_flag -= 1\n",
    "            if right_flag <= left_flag :\n",
    "                break\n",
    "        left_flag += 1\n",
    "        while left_flag <= right_flag :\n",
    "            if directions[left_flag] == 'L' : ans += left.get(directions[left_flag - 1],0)\n",
    "            elif directions[left_flag] == 'S':\n",
    "                if directions[left_flag - 1] == 'R': ans += 1\n",
    "            else :\n",
    "                if directions[left_flag - 1] == 'R': ans += 1\n",
    "            left_flag += 1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countCollisions(self, directions: str) -> int:\n",
    "        ans = 0\n",
    "        c1 = directions.count('RL')\n",
    "        ans += 2*c1\n",
    "        directions = directions.replace('RL', 'S')\n",
    "        idx = directions.find('S')\n",
    "        if idx != -1:\n",
    "            ans += directions[idx:].count('L')\n",
    "        idx = directions[::-1].find('S')\n",
    "        if idx != -1:\n",
    "            ans += directions[:len(directions)-idx-1].count('R')\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def countCollisions(self, directions: str) -> int:\n",
    "        n = len(directions)\n",
    "        ans = 0\n",
    "        pre = directions[0]\n",
    "        for w in directions[1:]:\n",
    "            if w == \"L\":\n",
    "                if pre in \"RS\":\n",
    "                    ans += 1\n",
    "            else:\n",
    "                pre = w\n",
    "\n",
    "\n",
    "        pre = directions[-1]\n",
    "        for w in directions[:-1][::-1]:\n",
    "            if w == \"R\":\n",
    "                if pre in \"LS\":\n",
    "                    ans += 1\n",
    "            else:\n",
    "                pre = w\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countCollisions(self, directions: str) -> int:\n",
    "        direct = collections.deque(list(directions))\n",
    "        while direct and direct[0] == \"L\":\n",
    "            direct.popleft()\n",
    "        while direct and direct[-1] == \"R\":\n",
    "            direct.pop()\n",
    "        s_cnt = 0\n",
    "        for val in direct:\n",
    "            if val == \"S\": s_cnt += 1\n",
    "        return len(direct) - s_cnt"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countCollisions(self, directions: str) -> int:\n",
    "        s = deque()\n",
    "        ans = 0\n",
    "        for d in directions:\n",
    "            if d == \"R\":\n",
    "                s.append(d)\n",
    "            if d == \"L\":\n",
    "                if s:\n",
    "                    while s and s[-1] == \"R\":\n",
    "                        s.pop()\n",
    "                        ans += 1\n",
    "                    ans += 1\n",
    "                    s.append(\"S\")\n",
    "            if d == \"S\":\n",
    "                while s and s[-1] == \"R\":\n",
    "                    s.pop()\n",
    "                    ans += 1\n",
    "                s.append(d)\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countCollisions(self, directions: str) -> int:\n",
    "        stk = []\n",
    "        ans = 0\n",
    "        for i in directions:\n",
    "            if i=='R':\n",
    "                stk.append(i)\n",
    "            elif i=='L':\n",
    "                if not stk:\n",
    "                    stk.append(i)\n",
    "                elif stk and stk[-1]=='R':\n",
    "                    ans += 2\n",
    "                    stk.pop()\n",
    "                    while stk and stk[-1]=='R':\n",
    "                        ans += 1\n",
    "                        stk.pop()\n",
    "                    if not stk or (stk[-1]!='S'):\n",
    "                        stk.append('S')\n",
    "                elif stk and stk[-1]=='S':\n",
    "                    ans += 1\n",
    "            elif i=='S':\n",
    "                while stk and stk[-1]=='R':\n",
    "                    ans += 1\n",
    "                    stk.pop()\n",
    "                if not stk or (stk[-1]!='S'):\n",
    "                    stk.append(i)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countCollisions(self, directions: str) -> int:\n",
    "        stack = []\n",
    "        count =0\n",
    "        for d in directions:\n",
    "            if not stack:\n",
    "                if d == 'L':\n",
    "                    continue\n",
    "                stack.append(d)\n",
    "            else:\n",
    "                if d == 'L':\n",
    "                    if stack[-1] == \"S\":\n",
    "                        count+=1\n",
    "                    elif stack[-1] == \"R\":\n",
    "                        stack.pop()\n",
    "                        count+=2\n",
    "                        while stack and stack[-1]=='R':\n",
    "                            count+=1\n",
    "                            stack.pop()\n",
    "                        stack.append(\"S\")\n",
    "                elif d == 'S':\n",
    "                    if stack[-1] == \"R\":\n",
    "                        stack.pop()\n",
    "                        count+=1\n",
    "                        while stack and stack[-1]=='R':\n",
    "                            count+=1\n",
    "                            stack.pop()\n",
    "                        stack.append(\"S\")\n",
    "                else:\n",
    "                    stack.append(d)\n",
    "        return count"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countCollisions(self, cars: str) -> int:\n",
    "        n = len(cars)\n",
    "        stack = []\n",
    "        num_crash = 0\n",
    "        \n",
    "        for i in range(n):\n",
    "            #print(i,stack,cars[i])\n",
    "            #print(num_crash)\n",
    "\n",
    "            if cars[i] == \"R\":\n",
    "                stack += \"R\"\n",
    "            elif cars[i] == \"L\":\n",
    "                if stack:\n",
    "                    car_before = stack.pop()\n",
    "                    if car_before == \"R\":\n",
    "                        num_crash += 2\n",
    "                        while stack and stack[-1] == \"R\":\n",
    "                            num_crash += 1\n",
    "                            car_before = stack.pop()\n",
    "                        stack += \"S\"\n",
    "                    \n",
    "                    elif car_before == \"S\":\n",
    "                        num_crash += 1\n",
    "                        stack += \"S\"\n",
    "                \n",
    "            else :\n",
    "                if stack:\n",
    "                    car_before = stack.pop()\n",
    "                    if car_before == \"R\":\n",
    "                        num_crash += 1\n",
    "                        while stack and stack[-1] == \"R\":\n",
    "                            num_crash += 1\n",
    "                            car_before = stack.pop()\n",
    "                        stack += \"S\"\n",
    "                    elif car_before == \"S\":\n",
    "                        stack += \"S\"\n",
    "                else:\n",
    "                    stack += \"S\"\n",
    "        return num_crash\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countCollisions(self, directions: str) -> int:\n",
    "        n = len(directions)\n",
    "        ans = 0\n",
    "        st = []\n",
    "        for ch in directions:\n",
    "            if ch == 'R':\n",
    "                st.append(ch)\n",
    "            elif ch == 'L':\n",
    "                if st:\n",
    "                    if st[-1] == 'S':\n",
    "                        ans += 1\n",
    "                    elif st[-1] == 'R':\n",
    "                        ans += 2\n",
    "                        st.pop()\n",
    "                        while st and st[-1] == 'R':\n",
    "                            ans += 1\n",
    "                            st.pop()\n",
    "                        st.append('S')\n",
    "            else:\n",
    "                while st and st[-1] == 'R':\n",
    "                    ans += 1\n",
    "                    st.pop()\n",
    "                st.append(ch)\n",
    "\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countCollisions(self, directions: str) -> int:\n",
    "        st = []\n",
    "        ans = 0\n",
    "        for c in directions:\n",
    "            if st:\n",
    "                if st[-1] == 'L':\n",
    "                    st.pop()\n",
    "                    st.append(c)\n",
    "                elif st[-1] == 'S':\n",
    "                    if c == 'L':\n",
    "                        ans += 1\n",
    "                        st.pop()\n",
    "                        st.append('S')\n",
    "                    else:\n",
    "                        st.append(c)\n",
    "                else:\n",
    "                    while st and st[-1] == \"R\":\n",
    "                        if c == 'S':\n",
    "                            ans += 1\n",
    "                            st.pop()\n",
    "                        elif c == 'L':\n",
    "                            ans += 2\n",
    "                            st.pop()\n",
    "                            c = 'S'\n",
    "                        else:\n",
    "                            break\n",
    "                    st.append(c)\n",
    "            else:\n",
    "                st.append(c)\n",
    "        return ans\n",
    "                        \n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countCollisions(self, directions: str) -> int:\n",
    "        stk = []\n",
    "        ans = 0\n",
    "        for i in directions:\n",
    "            if i=='R':\n",
    "                stk.append(i)\n",
    "            elif i=='L':\n",
    "                if stk and stk[-1]=='R':\n",
    "                    ans += 2\n",
    "                    stk.pop()\n",
    "                    while stk and stk[-1]=='R':\n",
    "                        ans += 1\n",
    "                        stk.pop()\n",
    "                    stk.append('S')\n",
    "                elif stk and stk[-1]=='S':\n",
    "                    ans += 1\n",
    "            elif i=='S':\n",
    "                while stk and stk[-1]=='R':\n",
    "                    ans += 1\n",
    "                    stk.pop()\n",
    "                stk.append(i)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countCollisions(self, directions: str) -> int:\n",
    "        cnt = 0\n",
    "        stack = []\n",
    "        for d in directions:\n",
    "            if not stack:\n",
    "                stack.append(d)\n",
    "            else:\n",
    "                if d == 'S' and stack[-1] == 'R':\n",
    "                    while stack and stack[-1] == 'R':\n",
    "                        cnt += 1\n",
    "                        stack.pop()\n",
    "                    stack.append('S')   \n",
    "                elif d == 'L' and stack[-1] == 'R':\n",
    "                    cnt += 1\n",
    "                    while stack and stack[-1] == 'R':\n",
    "                        cnt += 1\n",
    "                        stack.pop()\n",
    "                    stack.append('S') \n",
    "                elif d == 'L' and stack[-1] == 'S':\n",
    "                    cnt += 1\n",
    "                else:\n",
    "                    stack.append(d)\n",
    "        \n",
    "        return cnt"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countCollisions(self, directions: str) -> int:\n",
    "        \n",
    "        stack = []\n",
    "        ans = 0\n",
    "        for d in directions:\n",
    "            # print(stack)\n",
    "            if d == 'L':\n",
    "                i = len(stack) - 1\n",
    "                while i >= 0 and stack[i] == 'R':\n",
    "                    stack[i] = 'S'\n",
    "                    i -= 1\n",
    "                    ans += 1\n",
    "                if stack and stack[-1] == 'S':\n",
    "                    ans += 1\n",
    "                    stack.append('S')\n",
    "                else:\n",
    "                    stack.append('L')\n",
    "\n",
    "            elif d == 'S':\n",
    "                i = len(stack) - 1\n",
    "                while i >= 0 and stack[i] == 'R':\n",
    "                    stack[i] = 'S'\n",
    "                    i -= 1\n",
    "                    ans += 1\n",
    "                stack.append('S')\n",
    "            else: \n",
    "                stack.append(d)\n",
    "        return ans\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countCollisions(self, directions: str) -> int:\n",
    "        res = 0\n",
    "        stack = []\n",
    "        for direction in directions:\n",
    "            if direction=='L':\n",
    "                if stack and stack[-1]=='R':\n",
    "                    res += 2\n",
    "                    stack.pop()\n",
    "                    while stack and stack[-1]=='R':\n",
    "                        res += 1\n",
    "                        stack.pop()\n",
    "                    stack.append('S')\n",
    "                elif stack and stack[-1]=='S':\n",
    "                    res += 1\n",
    "            elif direction=='S':\n",
    "                while stack and stack[-1]=='R':\n",
    "                    res += 1\n",
    "                    stack.pop()\n",
    "                stack.append('S')\n",
    "            else:\n",
    "                stack.append('R')\n",
    "\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countCollisions(self, directions: str) -> int:\n",
    "        ans = 0\n",
    "        s = []\n",
    "        for ch in directions:\n",
    "            nxt = ch\n",
    "            while 1:\n",
    "                if nxt == 'R':\n",
    "                    s.append(nxt)\n",
    "                    break\n",
    "                elif nxt == 'S':\n",
    "                    if s and s[-1] == 'R':\n",
    "                        ans += 1\n",
    "                        s.pop()\n",
    "                    else:\n",
    "                        s.append(nxt)\n",
    "                        break\n",
    "                else:\n",
    "                    if s:\n",
    "                        if s[-1] == 'S':\n",
    "                            ans += 1\n",
    "                            break\n",
    "                        elif s[-1] == 'R':\n",
    "                            ans += 2\n",
    "                            nxt = 'S'\n",
    "                            s.pop()\n",
    "                    else:\n",
    "                        break\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countCollisions(self, directions: str) -> int:\n",
    "        #解题思路：\n",
    "        #两辆车移动方向相同，不会发生碰撞，移动方向相反，不管相距多远，一定会发生碰撞\n",
    "        #单调栈\n",
    "        #如果当前车向左，之前车方向向右/静止，一定会碰撞，碰撞后状态为S\n",
    "        #如果当前车向右，入栈\n",
    "        #如果当前车静止，之前车向右，碰撞\n",
    "\n",
    "        stack = []\n",
    "        res = 0\n",
    "        for x in directions:\n",
    "            if not stack:\n",
    "                stack.append(x)\n",
    "                continue\n",
    "            if x == 'L':\n",
    "                if stack and stack[-1] == 'S':\n",
    "                    res += 1\n",
    "                elif stack and stack[-1] == 'R':\n",
    "                    res += 2\n",
    "                    stack.pop()\n",
    "                    x = 'S'\n",
    "            if x == 'S':\n",
    "                while stack and stack[-1] == 'R':\n",
    "                    res += 1\n",
    "                    stack.pop()\n",
    "                stack.append('S')\n",
    "            if x == 'R':\n",
    "                stack.append('R')\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countCollisions(self, directions: str) -> int:\n",
    "        n = len(directions)\n",
    "        ans = 0\n",
    "        lst = list(directions)\n",
    "        res = 0\n",
    "        for i in range(n-1):\n",
    "            if lst[i] ==  'S' and lst[i+1] == 'L':\n",
    "                ans += 1\n",
    "                lst[i+1] = 'S'\n",
    "            elif lst[i] == 'R':\n",
    "                if lst[i+1] == 'S':\n",
    "                    ans += res + 1\n",
    "                    lst[i+1] = 'S'\n",
    "                    res = 0\n",
    "                elif lst[i+1] == 'L':\n",
    "                    ans += res + 2\n",
    "                    lst[i+1] = 'S'\n",
    "                    res = 0\n",
    "                else:\n",
    "                    res += 1\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countCollisions(self, directions: str) -> int:\n",
    "        stack = []\n",
    "\n",
    "        res = 0 \n",
    "\n",
    "        for d in directions:\n",
    "            if not stack:\n",
    "                stack.append(d)\n",
    "            else:\n",
    "                if d == 'L':\n",
    "                    if stack[-1] == 'R':\n",
    "                        res += 2\n",
    "                        stack.pop()\n",
    "\n",
    "                        while stack and stack[-1] == 'R':\n",
    "                            res += 1\n",
    "                            stack.pop()\n",
    "\n",
    "                        stack.append('S')\n",
    "                    elif stack[-1] == 'S':\n",
    "                        res += 1\n",
    "                        stack.append('S')\n",
    "                    else:\n",
    "                        stack.append('L')\n",
    "                elif d == 'S':\n",
    "                    while stack and stack[-1] == 'R':\n",
    "                        stack.pop()\n",
    "                        res += 1\n",
    "                    stack.append('S')\n",
    "                elif d == 'R':\n",
    "                    stack.append('R')\n",
    "\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countCollisions(self, directions: str) -> int:\n",
    "        n = len(directions)\n",
    "        ans = 0\n",
    "        lst = list(directions)\n",
    "        res = 0\n",
    "        for i in range(n-1):\n",
    "            if lst[i] ==  'S' and lst[i+1] == 'L':\n",
    "                ans += 1\n",
    "                lst[i+1] = 'S'\n",
    "            elif lst[i] == 'R':\n",
    "                if lst[i+1] == 'S':\n",
    "                    ans += res + 1\n",
    "                    lst[i+1] = 'S'\n",
    "                    res = 0\n",
    "                elif lst[i+1] == 'L':\n",
    "                    ans += res + 2\n",
    "                    lst[i+1] = 'S'\n",
    "                    res = 0\n",
    "                else:\n",
    "                    res += 1\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countCollisions(self, directions: str) -> int:\n",
    "       q=[]\n",
    "       d=[]\n",
    "       i=0\n",
    "       for x in directions:\n",
    "          if x!='L':\n",
    "            break\n",
    "          i+=1\n",
    "       j=len(directions)   \n",
    "       for x in directions[::-1]:\n",
    "          if x!='R':\n",
    "             break\n",
    "          j-=1                 \n",
    "       for x in directions[i:j]:\n",
    "           if x =='S':\n",
    "               q.append(0)\n",
    "           else:\n",
    "               q.append(1)\n",
    "       f=sum(q)\n",
    "       e=list(directions[i:j])\n",
    "       ans=0\n",
    "    #    while f:\n",
    "    #       for i in range(len(e)):\n",
    "    #           if i<len(e)-1 and e[i]=='R' and e[i+1]=='L':\n",
    "    #               f-=2\n",
    "    #               e[i]='S'\n",
    "    #               e[i+1]='S'\n",
    "    #               ans+=2\n",
    "    #           elif i<len(e)-1 and e[i]=='R' and e[i+1]=='S':\n",
    "    #               f-=1\n",
    "    #               e[i]='S'\n",
    "    #               ans+=1  \n",
    "    #           elif i>0 and e[i]=='L' and e[i-1]=='S':\n",
    "    #               e[i]='S'\n",
    "    #               f-=1\n",
    "    #               ans+=1\n",
    "       return f           \n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countCollisions(self, directions: str) -> int:\n",
    "        dir_len = len(directions)\n",
    "        left, right = 0, dir_len\n",
    "        for i in directions:\n",
    "            if i == \"L\":\n",
    "                left += 1\n",
    "            else:\n",
    "                break\n",
    "        for j in list(reversed(directions)):\n",
    "            if j == \"R\":\n",
    "                right -= 1\n",
    "            else:\n",
    "                break\n",
    "        sub_directions = directions[left:right]\n",
    "        S_count = 0\n",
    "        for i in sub_directions:\n",
    "            if i == 'S':\n",
    "                S_count += 1\n",
    "        return len(sub_directions) - S_count\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countCollisions(self, directions: str) -> int:\n",
    "        dir_len = len(directions)\n",
    "        left, right = 0, dir_len\n",
    "        for i in directions:\n",
    "            if i == \"L\":\n",
    "                left += 1\n",
    "            else:\n",
    "                break\n",
    "        for j in list(reversed(directions)):\n",
    "            if j == \"R\":\n",
    "                right -= 1\n",
    "            else:\n",
    "                break\n",
    "        sub_directions = directions[left:right]\n",
    "        S_count = 0\n",
    "        for i in sub_directions:\n",
    "            if i == 'S':\n",
    "                S_count += 1\n",
    "        return len(sub_directions) - S_count\n",
    "            "
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
